public class HashBuck {
    public class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] array;
    public int usedSize;

    public HashBuck(){
        array = new Node[10];
    }

    public void put(int key, int val){
        int index = key % array.length;
        Node node = new Node(key,val);

        Node cur = array[index];
        //此时没有节点
        if(cur == null){
            array[index] = node;
            usedSize++;
            return;
        }
        //找到尾巴
        while (cur.next != null){
            //更新val值
            if(cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        if(cur.key == key){
            cur.val = val;
            return;
        }
        cur.next = node;//进行插入
        usedSize++;


        if( loadFactor() > 0.75){
            resize();//扩容
        }
    }

    private void resize(){
        Node[] tmpArr = new Node[array.length * 2];
        //遍历原来的数组 将原来的数字重新哈希

        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];

            while (cur!= null){

                int newIndex = cur.key % tmpArr.length;

                if(tmpArr[newIndex] == null){
                    tmpArr[newIndex] = cur;
                    //插完 cur向下走一步
                    //cur = cur.next
                }else {

                    Node cur2 = tmpArr[newIndex];
                    while (cur2.next != null){
                        cur2 = cur2.next;//cur向下移

                    }
                    cur2.next = cur;
                    //插完 cur向下移
                }

                cur = cur.next;//if else 都右这一步 所以写到这里
            }
        }

        array = tmpArr;
    }

    //负载因子
    private double loadFactor(){
        return usedSize *1.0 / array.length;
    }

    public int get(int key){
         int index = key % array.length;
         Node cur = array[index];
         while (cur != null){
             if(cur.key == key){
                 return cur.val;
             }
             cur = cur.next;
         }
         return -1;
    }
}
